package 算法_100.简单;

/**
 * @Title 统计素数个数
 * 质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数，最小的素数是2
 * 重点：埃筛法
 * @Author zhengqiang.tan
 * @Date 1/6/23 10:38 PM
 */
public class A1_统计素数个数 {
    public static void main(String[] args) {
        int x = 100;
        System.out.println("暴力解法(x) = " + bruteForceSolution(x));
        int x1 = 5;
        System.out.println("isPrime(x1) = " + isPrime(x1));
        System.out.println("eratosthenes(100) = " + eratosthenes(100));
    }

    //暴力解法1
    public static int bruteForceSolution(int x) {
        int count = 0;
        for (int i = 2; i < x; i++) {
            count += isPrime(i) ? 1 : 0;
        }
        return count;
    }

    // 判断是否是素数
    public static boolean isPrime(int x) {
        if (x < 2) return false;
        // 优化：i<根x即可 i * i < x 等价于 i<根x 不用i<x 太浪费遍历次数了，
        // 原因：12 （2x6 3x4 根12x根12  4x3 6x2）只需要遍历到跟12位置即可。
        for (int i = 2; i * i < x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    // 重点：埃筛法
    public static int eratosthenes(int n) {
        boolean [] isPrime = new boolean[n]; // false代表素数
      int count = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                count++;
                for (int j=2*i;j<n;j+=i) { // j合数的标记位置
                    isPrime[j] = true;
                }
            }
        }
        return count;
    }

}
